﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.IO;

namespace StringMatch
{
    public class PrimeTable : List<UInt32>
    {







        public PrimeTable(UInt32 max, String fileName = null)
        {
            if (fileName != null && File.Exists(fileName))
            {
                StreamReader reader = new StreamReader(fileName);
                String line = reader.ReadLine();
                while (line != null)
                {
                    UInt32 prime = Convert.ToUInt32(line);
                    if (prime > max)
                        break;
                    this.Add(prime);
                    line = reader.ReadLine();
                }
                reader.Close();
            }
            else if (fileName != null)
            {

                var writer = new StreamWriter(fileName);
                for (UInt32 i = 5; i < max; i++)
                {
                    if (IsPrime(i))
                    {
                        Add(i);

                        writer.WriteLine(i);
                    }
                }
                writer.Close();
            }
            else
            {
                for (UInt32 i = 5; i < max; i++)
                {
                    if (IsPrime(i))
                        Add(i);

                }

            }


        }






        public static UInt64 EXPMOD(UInt32 a, UInt32 m, UInt32 n) // a^m mod n
        {
            BitArray bits = new BitArray(BitConverter.GetBytes(m));
            Int32 k = 0;
            while (m != 1)
            {
                m >>= 1;
                k++;
            }
            UInt64 c = 1;
            for (Int32 i = k; i >= 0; i--)
            {
                c = (c * c) % n;
                if (bits[i])
                    c = (a * c) % n;
            }

            return c;
        }

        public static Boolean Witness(UInt32 a, UInt32 n, UInt32 q, UInt32 m)
        {
            UInt64 x = EXPMOD(a, m, n);
            if (x == 1)
                return false;
            for (Int32 i = 1; i <= q; i++)
            {
                if (x == n - 1)
                    return false;
                x = (x * x) % n;
                if (x == 1)
                    return true;
            }
            return true;
        }

        public static Boolean IsPrime(UInt32 n)
        {
            UInt32 m = n - 1;
            UInt32 q = 0;
            while ((m & 0x00000001) != 0x00000001)
            {
                q++;
                m >>= 1;
            }
            Random r = new Random();
            UInt32 k = Convert.ToUInt32(Math.Ceiling(Math.Log(n)));

            for (UInt32 i = 0; i < k; i++)
            {
                UInt32 a = Convert.ToUInt32(Math.Round(r.NextDouble() * (n - 4))) + 2;
                if (Witness(a, n, q, m))
                    return false;

            }
            return true;

        }
    }
}
